/*
 * @lc app=leetcode.cn id=787 lang=typescript
 *
 * [787] K 站中转内最便宜的航班
 */

// @lc code=start

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number
): number {
  const INF = Number.POSITIVE_INFINITY;
  let dp = new Array(n).fill(INF);
  // 原地不动，消耗0，路过的边数也是0
  dp[src] = 0;
  let ans = INF;
  // 遍历，经过t条边，各个路径的消耗最小值
  for (let t = 1; t <= k + 1; t++) {
    const temp = new Array(n).fill(INF);
    for (const [from, to, price] of flights) {
      temp[to] = Math.min(temp[to], dp[from] + price);
    }
    dp = temp;
    ans = Math.min(ans, dp[dst]);
  }
  return ans === INF ? -1 : ans;
}
// @lc code=end
